package edu.dayu.demo2;

/**
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * 输入：cost = [10, 15, 20]
 * 输出：15
 * 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
 * 题目的理解： 刚开始自身为 -1，每次可以选择走 1、2 步。然后计算出，经过路径之和最小的方案。
 *
 * 思路：这种题感觉只能 动态规划 情况。
 * 思路2：使用递归把所有情况遍历一边，超时了。
 */
public class 爬楼梯的最少成本 {
    static int min = 0;
    static boolean flag = false;
    public static void main(String[] args) {
        int[] cost = {10,15,20};
        System.out.println(minCostClimbingStairs(cost));
    }

    public static int minCostClimbingStairs(int[] cost) {
//        dfs(cost,-1,0);
//        return min;

        int len = cost.length;
        int[] dp = new int[len];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < len; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i];
        }
        return Math.min(dp[len-1],dp[len-2]);
    }



    /**
     * 超时了
     */
    public static void dfs(int[] cost,int t,int sum){
        if (t>=cost.length) {
            if (!flag||sum<min) {
                flag =true;
                min = sum;
            }
            return;
        }
        for (int i = 1;i<3;i++){
            if (t>=0)
            sum+=cost[t];
            dfs(cost,t+i,sum);
            if (t>=0)
            sum-=cost[t];
        }
    }
}
